package com.hy.day;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:2831. 找出最长等值子数组
 * 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
 * 如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
 * 从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
 * 子数组 是数组中一个连续且可能为空的元素序列。
 * User:Mr.Du
 * Date:2024/5/23
 * Time:01:14
 */
public class LongestEqualSubarray {

    /**
     * 查找数组中最长的与给定值k相等的子数组长度。
     *
     * @param nums 包含整数的列表，代表输入数组。
     * @param k 给定的值，用于查找与之相等的子数组。
     * @return 返回数组中最长的与给定值k相等的子数组的长度。
     */
    public int longestEqualSubarray(List<Integer> nums, int k) {
        // 初始化变量n为数组长度，并创建一个数组来存储每个数字出现的位置列表。
        int n = nums.size(), ans = 0;
        List<Integer>[] posLists = new ArrayList[n + 1];
        Arrays.setAll(posLists, i -> new ArrayList<>());
        // 遍历数组，记录每个数字出现的位置。
        for (int i = 0; i < n; i++) {
            int x = nums.get(i);
            posLists[x].add(i);
        }
        for (List<Integer> pos : posLists){
            System.out.println(pos);
        }
        // 遍历每个数字的位置列表，计算最长的与k相等的子数组长度。
        for (List<Integer> pos : posLists) {
            // 如果当前位置列表的长度小于等于ans，则跳过，因为无法让ans变得更大。
            if (pos.size() <= ans) {
                continue;
            }
            int left = 0;
            // 使用双指针技巧来计算最长子数组长度。
            for (int right = 0; right < pos.size(); right++) {
                // 当右指针和左指针之间的距离大于k时，左指针向右移动。
                while (pos.get(right) - pos.get(left) - (right - left) > k) {
                    left++;
                }
                // 更新ans为当前子数组长度的最大值。
                ans = Math.max(ans, right - left + 1);
            }
        }
        // 返回最长子数组的长度。
        return ans;
    }

    public static void main(String[] args) {

        List<Integer> nums = new ArrayList<>(Arrays.asList(1,3,2,3,1,3));
        int k = 2;
        System.out.println(new LongestEqualSubarray().longestEqualSubarray(nums, k));
    }
}
